\section{Expanders}
\label{sec:exp}

For expander graphs, we  prove a high probability cover
time  of $O(\log^2 n)$. We break the proof up into two
phases. In the first phase we show that a cobra walk starting from any
vertex will reach a constant fraction of the vertices in logarithmic time
w.h.p. In the second phase, we create a process which stochastically
dominates the cobra walk and show that this new process will cover
the entire rest of the graph again in polylogarithmic time w.h.p.

The main result of this section can be stated in the following two
theorems, which when taken together imply that
w.h.p. $\epsilon$-expander $G$ will be covered in $O(\log^2 n)$ time.
We recall that $d$-regular $\eps$-expanders are defined in
Definition~\ref{def:exp}, and Theorem~\ref{thm:tanner} places a lower
bound on the size of neighborhoods in such an expander.

\begin{theorem}
\label{exp:phaseI}
Let $G$ be any $d$-regular $\epsilon$-expander with $\epsilon, \delta$
not depending on $n$ (number of vertices in $G$), with $\delta <
\frac{1}{2}$, and $\epsilon$, a sufficiently small constant such
that
\begin{equation}
\frac{1}{\epsilon^2 (1 - \delta) + \delta} >  \frac{d( d e^{-k} + (k-1)) - \frac{k^2}{2}}{d(e^{-k} + (k-1)) - \frac{k^2}{2}} , \\
\end{equation}
then in time $O(\log n)$, w.h.p. a cobra walk on $G$ with branching
factor $k$, will attain an active set of
size $\delta n$.
\end{theorem}
We note that the condition in the above theorem is satisfied if either
$\epsilon$ is sufficiently small, or $k$ is sufficiently large.  For
instance when $k = 2$, the above condition holds for strong expanders,
such as the Ramanujan graphs, which have $\epsilon \leq
2\sqrt{d-1}/d$, and random $d$-regular graphs, for $d$ sufficiently
large.

\begin{theorem}
\label{exp:phaseII}
Let $G$ be as above, and let W be a cobra walk on $G$ that at time T has reached an active set of size $\delta n$. Then w.h.p in 
an additional $O(\log^2 n)$ steps every vertex of $G$ will have visited by W at least once.
\end{theorem}   

To prove Theorem~\ref{exp:phaseI}  we prove that active sets up to a constant fraction of $V$ are growing at each step by a 
factor greater than one. \onlyShort{The proof can be found in the full version.} 

\begin{lemma}
\label{exp:expect}
Let $G$ be any $\epsilon$-expander with $\epsilon, \delta$ satisfying the conditions of Theorem~\ref{exp:phaseI}. Then for any 
time $t  \geq 0$, the cobra walk on $G$ with active set $S_t$ such that $|S_t| \leq \delta n$ satisfies $\E[|S_{t+1}|] \geq (1+\nu)|
S_t|$ for some constant $\nu > 0$. 
\end{lemma}

\onlyLong{

\begin{proof}
We will instead show that the portion of $N(S_t)$ not selected by the cobra walk is sufficiently small, $\E[|N(S_t) - S_{t+1}|] \leq |
N(S_t)| - (1+\nu)|S_t|$, and the result of the lemma will follow immediately. 

For each vertex $u \in N(S_t)$, define $X_u$ as an indicator random variable that takes value 1 if $u \notin S_{t+1}$ and 0 
otherwise.  Then $\prob{X_u = 1} = (1-1/d)^{k d_u}$, where $d_u$ is the number of neighbors $u$ has in $S_t$. Thus:
$$\E[|N(S_t) - S_{t+1}|] = \sum_{u \in N(S_t)} X_u = \sum_{u \in N(S_t)} (1 - \frac{1}{d})^{k d_u} \leq \sum_{u \in N(S_t)} e^{-\frac{k 
d_u}{d}}.$$ 
Because $\sum_{u \in N(S_t)} d_u  = d |S_t|$ and we are working with a convex function, we have that $\sum e^{-\frac{kd_u}{d}}
$ is maximized when all the values of $d_u$ are equal to either $1$ or $d$, with the exception of possibly one $d_u$ to act as 
the remainder. Let $R_1$ be the number of vertices in $N(S_t)$ where $d_u = 1$, and let $R_2$ be the number of vertices where 
$d_u = d$. We have the following system of equations:
\begin{eqnarray}
R_1 + R_2 &=& |N(S_t)| \\
R_1 + d R_2 &=& d |S_t| 
\end{eqnarray}
solving for $R_1$ and $R_2$, we get:
\begin{eqnarray}
R_1 &=& \dfrac{d}{d-1} (|N(S_t)| - |S_t|) \\
R_2 &=& \dfrac{1}{d-1} (d|S_t| - |N(S_t)|).
\end{eqnarray}
We now want to show that 
$$\E[|N(S_t) - S_{t+1}|] \leq R_1 e^{-\frac{k}{d}} + R_2 e^{-k}
				= \dfrac{d}{d-1}(|N(S_t)| - |S_t|) e^{-\frac{k}{d}} + \dfrac{1}{d-1} (d |S_t| - |N(S_t)|)e^{-k}$$ 
				$$\leq |N(S_t)| - (1+\nu)|S_t|.$$
Rearranging, we want to show that
\begin{eqnarray*}
 |N(S_t)|\left( 1 - \dfrac{d}{d-1} e^{-\frac{k}{d}} + \dfrac{1}{d-1} e^{-k} \right) +  |S_t| \left(\dfrac{d}{d-1} e^{-\frac{k}{d}} - \dfrac{d}{d-1} e^{-k} - 1 \right) \geq \nu |S_t|.
\end{eqnarray*}
We let $\alpha = \frac{1}{\epsilon^2 (1-\delta) + \delta}$, then $|N(S_t)| \geq \alpha |S_t|$  (by Theorem \ref{thm:tanner}) and we can divide through by $|S_t|$ in 
the expression immediately above. Since the first quantity in parenthesis is positive, and we don't care what $\nu$ is as long as 
it's a positive constant, we are down to needing:
$\alpha \left( 1 - \dfrac{d}{d-1} e^{-\frac{k}{d}} + \dfrac{1}{d-1} e^{-k} \right) + \left(\dfrac{d}{d-1} e^{-\frac{k}{d}} - \dfrac{d}{d-1} e^{-k} 
-1\right) > 0$.
Rearranging, we want
\begin{displaymath}
\label{exp:penult}
(\alpha - 1) \left(1 - \dfrac{d}{d-1} e^{-\dfrac{k}{d}} \right) - \dfrac{d-\alpha}{d -1} e^{-k} > 0.
\end{displaymath}
Taking the second-order Taylor approximation $e^{-\frac{k}{d}} \leq 1 - \frac{k}{d} + \frac{k^2}{2d^2}$, (\ref{exp:penult}) will be 
satisfied if 
\begin{displaymath}
(\alpha - 1) \left(1- \dfrac{d}{d-1} \left( 1 - \frac{k}{d} + \dfrac{k^2}{2d^2} \right) \right) - \dfrac{d - \alpha}{d -1} e^{-k} > 0
\end{displaymath}
which will be true for 
\begin{displaymath}
\frac{1}{\epsilon^2 (1 - \delta) + \delta} = \alpha > \frac{ d( d e^{-k} + (k-1)) - \frac{k^2}{2}}{d(e^{-k} + (k-1)) - \frac{k^2}{2}}  \\
\end{displaymath}
\end{proof}
}

%Note that these results will only hold for fairly strong expanders. It
%is known that the Ramanujan graphs have $\epsilon \leq 2\sqrt{d-1}/d$,
%which for suitable $d$ is more than enough to satisfy this bound.
%On the other hand, the $p$-cycle graph constructed form $\mathbb{Z}_m$, where each number $i$ is linked to $i+1$ and 
%$i-1$ and its multiplicative inverse mod $m$, though an expander, is too weak to meet the bound in ~\ref{exp:expect}. 

Next, we use a martingale argument to show that the number of vertices in $S_t$ is concentrated around its expectation. 
\onlyShort{The proof of Lemma ~\ref{exp:martingale} can also be found in the full version of the paper.}

\begin{lemma}
\label{exp:martingale}
For a cobra walk on a $d$-regular $\epsilon$-expander that satisfies the conditions in Lemma ~\ref{exp:expect}, at any time $t$ 
\begin{equation}
\prob{|S_{t+1}| - \E[|S_{t+1}|] \leq -\tau |S_t|} \leq e^{-\dfrac{\tau^2 |S_t|}{2k}} 
\end{equation}
\end{lemma} 

\onlyLong{
\begin{proof}
Arbitrarily index the the vertices of $S_t$,   $i =  \{1,\ldots, |S_t| = m\}$. Let $(Z_i^j)$ be a sequences of random variables ranging 
over the indices $i$ and  $j = \{ 1, \dots, k \}$, where $Z_i^j = v$ indicates the $i^{th}$ element of $S_t$ has chosen vertex $v$ to 
place it's $j^{th}$ pebble. Define $A$ as the random variable that is the size of $S_{t+1}$. Then 
\begin{displaymath}
X^j_i = \E[A|Z^1_1,\ldots,Z_1^k,\ldots,Z_i^1,\ldots,Z_i^j]
\end{displaymath}
is the Doob martingale for $A$, with $X^k_m = |S_{t+1}|$. Since $X_i^j - X_i^{j-1} \leq 1$ and $X_{i}^1 - X_{i-1}^k \leq 1$ for all $i,j
$, Azuma's inequality yields:
\begin{equation}
\prob{|S_{t+1}| - \E[|S_{t+1}|] \leq -\tau |S_t|} \leq e^{-\frac{\tau^2 m^2}{2km}}  =  e^{- \frac{\tau^2 m}{2k}} 
\end{equation}
\end{proof} 
}

Finally, using the bound of Lemma~\ref{exp:martingale} we show that with high probability we will cover at least $\delta n$ of the 
vertices of $G$ with a cobra walk  in logarithmic time by showing that the active set for some $t = O(\log n)$ is of size at least $
\delta n$. 

\begin{lemma}
\label{exp:coinflips}
For a cobra walk on d-regular, $\epsilon$-expander $G$, there exists a time $T$ such that $T = O(\log n)$ and $|S_T| \geq \delta 
n$. 
\end{lemma}

The key to proving Lemma~\ref{exp:coinflips} is to view a cobra-walk on $G$ as a Markov process over a state space 
consisting of all of the possible sizes of the active set. In this interpretation, all configurations of pebbles in a cobra-walk in which 
$i$ vertices are active are equivalent.  The goal is to show that this new Markov process will reach a state corresponding to an 
active set of size $\delta n$ quickly w.h.p. To prove this, we first show that it is dominated by a restricted Markov chain over the 
same state space in which any negative growth in the size of the active set is replaced with a transition to the initial state (in 
which only one vertex is active). We then in turn show that the restricted walk is dominated by an even more restricted walk in 
which the probability of negative growth is higher than in the first restricted walk, bounded from below from a constant, and no 
longer dependent on the size of the current state. We then show that the goal of the lemma is achieved even in this walk by 
relating the process to a negative binomial random variable.

\begin{proof}
We view a cobra-walk on $G$ as a random walk $W$ over the state space consisting of all of the possible sizes of the active set: 
$S(W) = \{1,\ldots,n\}$. We then define a Markov process $M_1$ that stochastically dominates $W$: Let $\tau = \nu/2$, where $
\nu$ is the expected growth factor of the active set as shown in Lemma~\ref{exp:expect}. The states of $M_1$, $S(M_1)$ are the 
same as $W$'s, but the transitions between states differ. Each $i \in S(W)$ can have out-arcs to many different states, but the 
corresponding $i \in S(M_1)$ has only two transitions. With probability $p_i = 1 - e^{-\frac{\nu^2 i}{8k}}$ transition to state $(1 + 
\nu/2)i$, and with probability $1-p_i$ transition to state $1$. Note that $p_i$ is derived from Lemma~\ref{exp:martingale}.

In $M_1$, each transition probability is still a function of the current state $i$, and as mentioned above we would like to 
eliminate this dependence. Thus, define $M_2$ as a random walk over the same state space. However, we will deal only with a 
subset of $S(M_2)$: the states: $(1+\nu/2)^i C$ for $i \in \mathbb{Z}$ and a suitably large constant $C$. We then have the 
following transitions for each state in the chain (which will begin once it hits $C$). Setting $r = \nu^2/8k$, at state $(1+\nu/2)^i C:
$ 1) Transition to state $(1+\nu/2)^{i+1}C$ with probability $p'_i  = 1 - e^{-r C (1 + \frac{i \nu}{2})}$ 2) Transition to state $C$ with 
probability $1-p'_i$. This Markov chain oscillates between  failure (going to $C$) and growing by a factor of $1+\nu/2$. Note that 
to get success (i.e., reaching a state of at least $\delta n$), we need $\Omega(\log n)$ growing transitions.   

The probability that in a walk on this state space that we ``fail" and go back to $C$ before hitting $\delta n$ is bounded by $1/2$, 
since  $\sum_{i=0}^{\infty} e^{-rC(1+i\frac{\nu}{2})} \leq e^{-rC} \sum_{i=0}^{\infty} e^{i rC \frac{\nu}{2}} = \frac{e^{-rC}}{1 - e^{-rC
\frac{\nu}{2}}} \leq \frac{1}{2}$, provided that $C$ is sufficiently large as a function of $r$ (which is itself only a function of the 
branching factor and the constant $\nu$). 

Consider each block of steps that end in a failure (meaning we return to $C$).  Then clearly w.h.p. after $b \log n$ trials, for 
some constant $b$, we will have a trial that ends in success (i.e., reaching an active set of size $\delta n$ vertices). In these $b 
\log n$ trials, there are exactly that many returns to $C$. However, looking across all trials that end in failure, there are also only 
a total of $O(\log n)$ steps that are successful (i.e.,  involve a growth rather than shrinkage). To see why this is true, note that the 
probability of a failure after a string of growth steps goes down supralinearly with each step, so that if we know we are in a failing 
trial it is very likely that we fail after only a few steps. Thus, there cannot be too many successes before each failure. Indeed, the 
probability that we fail at step $i$ within a trial can be bounded. Thus, $\prob{\text{Failure at step } i  | \text{ eventual failure}}$

\begin{eqnarray*}
 &=&  \frac{\prob{\text{Failure at step i}}}{\prob{\text{Eventual failure}}} \\
 &=& \frac{ e^{-rC(1 + i \nu /2) }}{\sum_{i=1}^{\infty} \left(\prod_{j=1}^{l-1} (1 - e^{-rC(1+j \nu/2)}\right) e^{-rC(1+l \nu/2)}} \\
 &\geq& \frac{1}{ \sum_{i=1}^{\infty} e^{- i r C \nu/2}} \geq 1 - e^{-rC\nu/2}
\end{eqnarray*}
and thus the probability of advancing is no more than \text{ } $e^{-r C \nu /2}$, also a quantity that does not depend on $i$.  This 
is a negative binomial random variable with distribution $w(k,p)$, the number of coin flips needed to obtain $k$ heads with 
heads probability $p$. Identifying heads with a failure (i.e. returning to $C$) and tails with making a growth transition, we have a 
random variable $w(k,p)$, the number of coin flips needed for $k$ failures with probability of failure $p  = 1 - e^{-r C \nu / 2}$. It is 
well known that $\prob{w(k,p) \leq m} = \prob{B(m,p) \geq  k}$, where $B(m,p)$ is the binomial random variable counting the 
number of heads within $m$ $p$-biased coin flips. Thus, $\prob{w(k,p) > m}=  \prob{B(m,p) < k}$. Setting $k = a \log n$ and $m 
= b \log n$,  we have, $\prob{B(m,p) \leq \E[B(m,p)] - t} = \prob{B(m,p) < pm -t}  \leq e^{\frac{-2 t^2}{m}}$. 
We let $k=pm-t$, and solving for $t$ we get $t = (pb -a) \log n$. This gives us 
$$\prob{B(m,p) < k)} \leq \frac{1}{n^{\frac{(pb - a)^2}{b}}},$$ establishing there are at most $O(\log n)$ success within  $O(\log n)
$ trials ending in failure. Via stochastic dominance this bound holds for our original cobra walk process.

\end{proof} 

Once the active set has reached size $\Omega(n)$, we need a different
method to show that the cobra-walk achieves full coverage in  $O(\log^2
n)$ time.  We can not simply pick a random pebble and restart the
cobra-walk from this point $O(\log n)$ times because we know nothing
about the distribution of the $\delta n$ pebbles after restart, and
the restarting method would require the pebbles to be i.i.d. uniform
across the vertices of $G$.  As a result, we are unable to establish a
straightforward bound on $h_{max}$ and invoke Matthew's Theorem.

Hence, we develop a different process, which we will call $W_{alt}$,
which stochastically dominates the cobra walk. In $W_{alt}$, no
more branching or coalescing occurs, and we also modify the transition
probabilities of the pebbles on a vertex-by-vertex basis, depending on the
number of pebbles at a vertex.

\begin{definition}
For any time $t$ and any collection of $S$ pebbles on $V$ (there can
be more than 1 pebble at a vertex), define \textbf{ $W_{alt}(t+1)$ }
as follows.  Let $A \subseteq V$ be the set of all vertices with 1
pebble at time $t$. Let $B \subseteq V$ be the set of all vertices
with exactly 2 pebbles, and let $C$ be the set of all vertices with
more than 2 pebbles. Then, (a) for every $v \in A$, the pebble at $v$
uniformly at random selects a vertex in $\Gamma(v)$ (the neighborhood of $v$ not including itself) and moves to it; (b)
for every $v \in B$, each pebble at $v$ uniformly at random selects a vertex  in $\Gamma(v)$ and moves to it; (c) for every $v \in C$,
arbitrarily index the pebbles at v. Then the first two pebbles each (index $1,2$) then pick a
neighbor $\in \Gamma(v)$ to move to, uniformly at random. Let $u,w$ be the two neighbors picked by pebbles $1,2$. (Note that $w=u$ 
is a possible outcome. The remaining pebbles (those with index $>2$), still in the same
time step, each independently pick $u$ or $w$ with probability $1/2$ and move to the vertex
they have selected.
\end{definition} 

The process $W_{alt}$ can be thought of as a kind of coalescing random walk in which the threshold for coalescence is three
pebbles on a vertex rather than the standard two, with the added condition that the third (and higher) token chooses which of the 
first two tokens to coalesce with by flipping an unbiased coin. 

Furthermore, at any time $t$ a vertex with  two  or more pebbles behaves locally exactly the same in $W_{alt}$ and a cobra walk. The divergence
in behavior occurs only for those vertices with one pebble. In $W_{alt}$ they behave like vertices participating in a simple random walk (or 
like vertices in a cobra walk in which both pebbles have chosen the same neighbor to move to in the next round. In light of these 
modifications, the active set of $W_{alt}$ at any time $t$ can be viewed as a (possibly proper) subset of the active set of a cobra walk on $G$ if both are
started from identical initial conditions (i.e. distribution of pebbles). Therefore, the probability that the cover time of $W_{alt}$ is greater than
some value $x$ is larger than the probability of the cover time of the cobra walk being greater than $x$. Thus, $W_{alt}$ stochastically dominates
the cobra walk when started from the same initial condition.

Thus if we can prove that the cover time of $W_{alt}$ on $G$ is $O(\log n)$ with high probability, this will imply that the cover time of
the cobra walk on $G$ has the same upper bound as well. 

If at time $t$ a vertex during process $W_{alt}$ has two or more pebbles, at each time step it behaves identically to a vertex
running a cobra walk. On the other hand, if there is only one pebble at vertex running $W_{alt}$ it acts like a simple random walk. 
Thus the number of active vertices at the next time step in $W_{alt}$ is a (possibly proper) subset of the vertices with pebbles if the 
graph were running the cobra walk instead. Since this will be true at every time step, $W_{alt}$ stochastically dominates the 
cobra walk w.r.t cover time $\tau$ of $G$, and it will be sufficient to prove the following:
\begin{theorem}
\label{exp:fullcoverage}
Let G be a bounded-degree $d$-regular $\epsilon$ -expander graph, with $\epsilon$ sufficiently high to satisfy the conditions in 
Lemma~\ref{exp:expect}. Let there be $\delta n$ pebbles distributed arbitrarily over $V$, with at most one pebble per vertex. Let 
$\delta < \dfrac{1}{2}$.  Let $\alpha_2$ be the second-largest eigenvalue of the adjacency matrix of $G$. From our $
\epsilon$-expander definition, $\alpha_2 \leq \epsilon d$. For every $\epsilon$, there exists constant $\beta$ that is the edge 
expansion constant of $\Gtensor$ (defined below).  Furthermore, let $s = \dfrac{88(d+1)^2}{\beta^2} \log n$.  
Starting from this configuration, the cover time of $W_{alt}$ on $G$ is $O(\log^2 n)$, with high probability.  
\end{theorem}

\begin{proof}
Our proof relies on showing that each vertex in $G$ has a constant
probability of being visited by at least one pebble during an epoch of
$W_{alt}$ lasting $\Theta(\log n)$ time. Once this has been
established, all vertices of $G$ will be covered w.h.p. after $O(\log n)$
epochs lasting $\Theta(\log n)$ steps each.

Define $E_i$ to be the event that pebble $i$ covers an arbitrary vertex $v$ at time $s$. We want to prove that the probability that 
$v$ is covered by at least one pebble, $\prob{\bigcup_i E_i}$, is constant.  For pebbles $i$ and $j$, we cannot assume that
$E_i$ and $E_j$ are independent, since the transition probabilities of the walks of $i$ and $j$ will not be independent if they are spatially and temporally co-located.
However, we can calculate an upper bound using a second-order inclusion-exclusion 
approximation:
\begin{equation*}
\prob{\bigcup_i E_i}
\geq \sum_i \prob{E_i} - \sum_{i \neq j} \prob{E_i \cap E_j}
\end{equation*}
As a marginal probability, $\prob{E_i}$ can be viewed as the probability that the (simple) random walk of pebble $i$ hits $v$ at time $s$. 
This is justified because if we only observe the movement of pebble $i$, at any time $t$, if $i$ is at vertex $w$, its probability of walking to each of $w$'s  $d$ neighbors is $1/d$, regardless of whether it is the first, second, or third pebble at $w$.
Since it reduces to analyzing a simple random walk, we only need to look at the elements of $z A^s$, where $A$ is the stochastic
transition matrix of the simple random walk on $G$ and 
$z$ is a vector with $z(l) = 1$ for the $l$, the position of pebble $i$ at the beginning of the epoch and $0$ in all other positions. 
In ~\cite{AAKKLT} it is proved in Lemma 4.8 that each coordinate of $A^{s'} z$ differs from $1/n$ by at most $\frac{1}{2n}$ for $s' 
= \frac{\ln{2n}}{\ln{\epsilon}}$. Since $s > s'$, this hold for our case as well. Thus $\prob{E_i} \geq  \frac{1}{2n}$.

Next we establish an upper bound for $\prob{E_j \cap E_i}$, the joint (and hence non-independent) walks of pebbles $i$ and $j$. For the purposes of this analysis, we will consider pebble $i$ to be the higher-priority pebble: that is, if at any time $i$ and $j$ are co-located at some vertex, we assume that $i$ has first priority and chooses a neighbor to move to in the next step independently with uniform probability. We assume that $j$ has third or lower priority, and will choose $i$'s destination with probability $1/2$ and thus with probability $1/2$ choose a neighbor uniformly at random.
We can view the walks of $i,j$ as a random walk on the tensor product  $\Gtensor$. The tensor product  has vertex set that is the Cartesian product $V(G) \times V(G)$. Vertex $(u,u')$ of $\Gtensor$ has an edge to $(v,v')$ if and only $(u,v)$ and $(u',v')$ are edges of $G$.
Note that the joint walk of $i,j$ on $G$ does not map to a simple random walk on $\Gtensor$ -- rather, it maps to a walk on a directed graph formed from $\Gtensor$ with weights chosen appropriately based on the process $W_{alt}$. We will show that this walk, viewed as a non-reversible, irreducible Markov chain, has a stationary distribution close to $1/n^2$, that it converges rapidly to the stationary distribution, and thus after $s$ steps, the probability that $i$ and $j$ are at the same vertex in $G$ is no more than $2/(n^2 + n) + 1/n^4$. 


With this result, we then have:
\begin{eqnarray*}
\prob{\bigcup E_i }
 &\geq& \sum_i \prob{E_i} - \frac{1}{2} \sum_{i \neq j} \prob{E_j \cap E_i } \\
&\geq& \delta n \frac{1}{2n} - \frac{1}{2}  \binom{\delta n}{2}\left( \frac{2}{n^2 + n}  + \frac{1}{n^4}\right) \\
&\geq& \frac{\delta}{2} - \frac{\delta}{4} (\delta n^2 - n)  \left( \frac{2}{n^2 + n}  + \frac{1}{n^4}\right) \\
&\geq& \frac{\delta}{2} - \frac{2 \delta^2}{4}
\end{eqnarray*}

which will be a constant for any $\delta < 1/2$ for sufficiently large $n$. The last inequality holds because the term $(\delta n^2 -n)/n^4$ is negligible and $2(\delta n^2 - n)/(n^2 + n) < 2\delta n /(n+1) < 2 \delta$.  
\end{proof}


\begin{lemma}
\label{directedmarkov} 
Let $G$ and $s$ be defined as in Theorem~\ref{exp:fullcoverage}. Let $i$ and $j$ be two pebbles walking on $G$ according to the rules of $W_{alt}$. If $E_i \cap E_j$ defined as the event in which $i$ and $j$ are both at arbitrary vertex $v \in G$ at time $s$, then $\prob{E_i \cap E_j} \leq 1/n^2$. 
\end{lemma}

\begin{proof}

Let $\Gtensor$ be the tensor product chain defined as above. 

We first make some observations about the structure of this graph. We note that there are two types of vertices of $\Gtensor$. The first type involves all vertices that have the form $(u,u)$, where $u\in V(G)$ A pebble at $(u,u)$ would correspond to two pebbles occupying $u$ in the paired walk of $i,j$ on $G$. We label this set $S_1$. The cardinality of $S_1$ is $n$. The remaining vertices, which below to set $S_2$, are of the form $(u,v)$ for $u \neq v$. There are $n^2 - n$ such vertices Also note that in the undirected graph $\Gtensor$, each vertex has degree $d^2$. Further, every vertex in $S_1$ will have $d$ neighbors also in $S_1$, by virtue of $G$ being $d$-regular.

Many of the spectral properties of $G$ apply to $\Gtensor$ as well. Primarily, because $G$ is an $\epsilon$-expander, the transition matrix of a simple random walk on $G$ has a constant second eigenvalue $\alpha_2(G)$ bounded away from $0$. It is well known (c.f.~\cite{LevinPeresWilmer2006}) that $\Gtensor$ will have $\alpha_2 (\Gtensor) = \alpha_2(G)$, which will will refer to as $\alpha_2$ henceforth. 

We now take the undirected graph $\Gtensor$ and transform it into a directed graph $D(\Gtensor)$ as follows. For every undirected edge $(x,y)$ in $\Gtensor$, replace it with 2 directed edges: $x \rightarrow y$ and $y \rightarrow x$. As mentioned, every vertex in $S_1$ will have $d$ neighbors also in $S_1$, meaning there will be one directed arc $x \rightarrow y$ for every vertex $x  \in S_1$ and $y \in N(x), y \in S_i$. We now add an additional $d$ copies of edge $x \rightarrow y$ for every such original edge.  It is relevant for analysis to note that because of the regularity of the subgraph of $\Gtensor$ induced on $S_1$, for every vertex in $D(\Gtensor)$, the number of out-edges will equal the number of in-edges, and hence $D(\Gtensor)$ is an Eulerian digraph. 

Furthermore, we can now calculate the transition probabilities of a random walk on $D(\Gtensor)$ where an outgoing edge from vertex $x$ is picked with probability $1/d(v)$. For all vertices in $S_2$, every transition occurs with probability $1/d^2$ as in the symmetric case. This includes edges from $S_2$ into $S_1$. On the other hand, the probabilities of transitions from vertices in $S_1$ are modified: The probability of transitioning from a vertex $x \in S_1$ to one of its $d^2 -d$ neighbors in $S_2$ is now $1/2d^2$, while the probability of transitioning to a neighbor in $S_1$ has become $(d+1)/2d^2$ on account of the multiple edges. We have thus constructed a walk on digraph $D(\Gtensor)$ that maps exactly to the joint walk of pebbles $i,j$ on $G$ according to the rules of $W_{alt}$. 

Because the walk on $D(\Gtensor)$ is irreducible, it has a stationary distribution $\pi$, which is the (normalized) eigenvector of the dominant eigenvalue of the transition matrix $M$ of the walk on $D(\Gtensor)$. Furthermore, because $D(\Gtensor)$ is Eulerian, the stationary distribution of vertex $x$ is exactly given by: $d^+(x)/m$, where $m$ is the number of edges. Therefore there are only two distinct values of the components of the stationary vector: for all $x \in S_1$, $\pi(x) = 2/(n^2 + n)$, while for all $y \in S_2$, $\pi(y)= 1/(n^2 + n)$.

Because $G$ and hence $\Gtensor$ have such nice spectral properties, and because $D(\Gtensor)$ represents a minor modification of $\Gtensor$, it would be reasonable to intuit that $D(\Gtensor)$ also has some of the same properties. Yet, one must proceed with caution when analyzing Markov chains on directed graphs, as some properties that hold for chains on undirected graphs do not carry through. However, following closely the work of~\cite{Chung05laplaciansand} we can verify that the random walk on $D(\Gtensor)$ converges rapidly to its stationary distribution. 


For succinctness of notation denote $\D = D(\Gtensor)$. Consider the function $F_{\pi}: E(\D) \rightarrow \Re$ given by $F_{\pi}(x,y) = \pi(x) P(x,y)$, where $\pi(x)$ is the $x$-th component of the stationary distribution of the walk on $\D$ and $P(x,y)$ is the associated transition probability moving from $x$ to $y$. Then $F_{\pi}$ is the \textbf{circulation} associated with the stationary vector as shown in Lemma 3.1 of ~\cite{Chung05laplaciansand}. Note that a circulation is any such function that satisfies a balance equation: $\sum_{u, u\rightarrow v} F(u,v) = \sum_{w,v\rightarrow} F(v,w)$. 

There is a Cheeger constant for every directed graph, defined as:
\begin{equation}
h(G) = \inf_S \frac{F_{\pi}(\partial S)}{\min\{F_{\pi}(S),F_{\pi}(\bar{S})\}}
\end{equation}

where $F_{\pi}(\partial S) = \sum_{u\in S,v\notin S} F(u,v)$, $F(v) = \sum_{u,u\rightarrow v} F(u,v)$ and $F(S) = \sum_{v \in S} F(v)$ for a set S. Furthermore, Theorem 5.1 of~\cite{Chung05laplaciansand} shows that the second eigenvalue, $\lambda$, of the Laplacian of $\D$ satisfies:
\begin{equation}
2 h(\D) \geq \lambda \geq \frac{h^2(\D)}{2}
\end{equation}
The Laplacian of a directed graph is defined slightly differently than for an undirected graph. However, because we will not use the Laplacian directly in our analysis, we refer the reader~\cite{Chung05laplaciansand} for the definition. We will directly bound the Cheeger constant for $\D$, and hence produce a bound on the second eigenvalue of the Laplacian. This second bound will then be used to provide a bound on the convergence of the chain to its stationary distribution. 

First, w.l.o.g., assume that $F_{\pi}(S)$ is smaller than its complement.  Furthermore assume that $S$ is the set that satisfies the $\inf$ condition in the Cheeger constant. We have $F_{\pi}(\partial S)  = \sum_{x \rightarrow y, x \in S, y \in \bar{S}} \pi(x) P(x,y)$, and $F_{\pi} = \sum_{x \rightarrow y, x \in S} \pi(x) P(x,y)$. The first sum occurs over all (directed) edges that cross the cut of $S$. Fortunately, we are already able to provide a lower bound on the size of this cut. Observing that $\D$ has at least as many edges crossing the cut as a cut on the equivalent set $S$ in $\Gtensor$, and recalling that $\Gtensor$ has second eigenvalue $\alpha_2$, we can appeal to $\alpha_2$ being bounded away from zero by a constant (by virtue of $G$'s expansion, recall) to state that there exists some constant $\beta$ (depending on $\alpha_2$) such that there are at least $\beta |S|$ edges crossing the cut. We can thus provide a lower bound for the entire Cheeger constant: 
\begin{eqnarray*}
h(\D) &=& \inf_S \frac{F_{\pi}(\partial S)}{\min\{F_{\pi}(S),F_{\pi}(\bar{S})\}} \\
&\geq& \dfrac{\beta |S| P_{min} \pi_{min}}{|S| P_{max} \pi_{max}} \\
&=& \beta \cdot \dfrac{\dfrac{1}{2d^2} \dfrac{1}{(n^2 + n)}}{\dfrac{d+1}{2d^2} \dfrac{2}{(n^2 + n)}} =  \dfrac{\beta}{2(d+1)}  
\end{eqnarray*}  
We can then apply the lower Cheeger inequality to have $\lambda \geq \dfrac{\beta^2}{8(d+1)^2}$.  We now show the rapid convergence (in logarithmic time) of the walk on $\D$ to the stationary distribution. To measure distance from the stationary distribution, we use the $\chi-$\textit{square-distance}: 
\begin{equation}
\Delta'(t) = \max_{y \in V(\D)} \left( \sum_{x \in V(G)} \dfrac{(P^t(y,x) - \pi(x))^2}{\pi(x)}\right)^{1/2}
\end{equation} 

It can be shown that a rapid convergence for $\Delta'$ implies a rapid convergence for the total variational distance, and thus the distribution of a random walk starting anywhere in $\D$ will be close to its stationary distribution for every vertex. 

We next apply Theorem 7.3 from~\cite{Chung05laplaciansand} which we state here for clarity: 
\begin{theorem} 
Suppose a strongly connected directed graph $G$ on $n$ vertices has Laplacian eigenvalues $0=\lambda_0 \leq \lambda_1 \leq \ldots \leq \lambda_{n-1}$. Then G has a lazy random walk with the rate of convergence of order $2 \lambda_1^{-1} (-\log \min_x \pi(x))$. Namely, after at most  $t \geq 2 \lambda_1^{-1}((-\log \min_x \pi(x) + 2c)$  steps, we have: 
\begin{equation*}
\Delta'(t) \leq e^{-c}
\end{equation*}
\end{theorem} 

Recall that we provided a constant lower bound for $\lambda$, the second-smallest eigenvalue of the Laplacian of $\D$. Hence we can apply it to the minimum running time of the random walk on $\D$ to show that after at most: 
\begin{equation*}
s = \dfrac{8(d+1)^2}{\beta^2} \left(\log(n^2 + n) + 4 \log n^2 \right) 
\end{equation*}
steps we will have $\Delta'(t) \leq \dfrac{1}{n^4}$ Therefore, for the random walk on $\D$, after a logarithmic number of steps $s$ (in $n$, the size of $G$), a walk that starts at any initial distribution on $V(\D)$ will be within $1/n^{-4}$ of the stationary distribution of any vertex. Mapping our analysis back directly to the coupled walk of $i,j$ on $G$,  $\prob{E_i \cap E_j} \leq 2/(n^2 + n) + 1/n^4$ when pebbles $i$ and $j$ start from any initial position. 

\end{proof}

 
